| 翻訳と辞書 |
| Greenwood–Gleason graph ： ウィキペディア英語版 |
Clebsch graph
In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge variant is the order-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968)〔J. J. Seidel, Strongly regular graphs with (−1,1,0) adjacency matrix having eigenvalue 3, Lin. Alg. Appl. 1 (1968) 281-298.〕 because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the order-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of , who used it to evaluate the Ramsey number ''R''(3,3,3) = 17.〔.〕〔(The Clebsch Graph on Bill Cherowitzo's home page )〕〔.〕
==Construction==
The order-5 folded cube graph (the 5-regular Clebsch graph) may be constructed by adding edges between opposite pairs of vertices in a 4-dimensional hypercube graph. (In an ''n''-dimensional hypercube, a pair of vertices are ''opposite'' if the shortest path between them has ''n'' edges.) Alternatively, it can be formed from a 5-dimensional hypercube graph by identifying together (or contracting) every opposite pair of vertices.
Another construction, leading to the same graph, is to create a vertex for each element of the finite field GF(16), and connect two vertices by an edge whenever the difference between the corresponding two field elements is a perfect cube.
The order-5 halved cube graph (the 10-regular Clebsch graph) is the complement of the 5-regular graph. It may also be constructed from the vertices of a 5-dimensional hypercube, by connecting pairs of vertices whose Hamming distance is exactly two. This construction produces two subsets of 16 vertices that are disconnected from each other; each is isomorphic to the 10-regular Clebsch graph.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Clebsch graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|